昨天我們寫了用 linear search 取兩array 間 intersection 的練習
若兩個 array 長度很長的話，其複雜度會為 O(lengthOfArrayOne*lengthOfArrayTwo)，其實這樣做效率並不好

今天來介紹一個名為 counter(計數器) 的概念

What is counter

• Counter is not a formal name.Name is different everywhere, but the idea is the same.
• Using a counter object will reduce the complexity of algorithms

Counter in the get intersection practice

所謂的 counter 顧名思義，就是建立一個物件紀錄『每個數字出現的次數』，當物件中的數字出現複數次，就表示『該數字為兩 array 的交集部分』

使用counter概念到我們將昨天的練習中..

提示：使用Counter

Answer:

const array1 = [1, 6, 3, 9, 17, 22, 18, 7, 5, 2, 21, 12, 37, 33, 8, 109, 77, 23, 14, 11];
const array2 = [2, 5, 8, 12, 75, 17, 23, 14, 36, 33, 7, 9, 77, 56, 62, 1, 102, 3,];

function getIntersection(arrA,arrB){
    const result=[], dataset=arrA.concat(arrB),counter={};
    for(let i=0;i<dataset.length;i++){
        if(!counter[dataset[i]]){
            counter[dataset[i]] =1;
        }else{
            counter[dataset[i]]++;
        }
    }
    // loop through counter object
    for(property in counter){
        if(counter[property]>1){
            result.push(Number(property));
        }
    }
    return result;
}

getIntersection(array1 , array2); // [1, 3, 9, 17, 7, 5, 2, 12, 33, 8, 77, 23, 14]

在使用 counter 後，我們將 getIntersection 的 Big O降至 O(lengthOfArrayOne+lengthOfArrayTwo)